/*
 * @作者: 沙昊
 * @邮箱: shahao@zju.edu.cn
 * @功能: 
 * @包含算法: 
 * Copyright (c) 2023 by 沙昊, All Rights Reserved. 
 */
//二叉树最近公共祖先
//这个是early stop的写法，需要定义一套返回值flag体系
class Solution {
private:
    TreeNode* result=nullptr;
    int  recursive(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return 0;

        int left = recursive(root->left, p, q);
        if(left==2) return 2;
        int right = recursive(root->right, p, q);
        if(right==2) return 2;

        int sum = left + right;
        if(root==p || root==q) sum += 1;
        if(sum==2){
            result = root;
        }
        return sum;
    }

public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        recursive(root,p,q);
        return result;
    }

};


//这个是返回值为 treenode的方法，无论如何必须要遍历完整棵树，无法提前结束；
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL) return root;

        if (left == NULL && right != NULL) return right;
        else if (left != NULL && right == NULL) return left;
        else  { //  (left == NULL && right == NULL)
            return NULL;
        }

    }
};